You've done a search problem success, which is something we can also do.

And it's the obvious thing we've already sketched.

So we have a search state and a search problem, and we have to kind of give the initial state,

the successor function, and the goal test.

So initial state is easy.

We start with the empty assignment.

The successor function is we just assign a value to the current assignment.

Just choose, and that's important, choose a variable and choose a value for that value.

So we have two choices here.

And making good choices is always important, as you know.

So any of the choice of a variable and then a value gives you a successor state unless

you violate a constraint.

Because the heuristics we're going to discover are things that we humans kind of instinctively

do.

I mean, humans are expert problem solvers.

And if we want to get close, we better watch the humans.

So that's the search.

Successor function is the successful, the consistent extensions.

You fail when there are no legal assignments anymore.

And the goal test is whether we have a total assignment.

The nice thing is that this setup is the same for all CSPs.

The particulars of the CSPs are essentially just the successor function.

That means consistent extensions, which gets the constraints and the domains and the variables

in there.

Another nice thing is all the solutions are at the same depth.

Because we're currently assuming that you're filling one variable at a time.

And the path is irrelevant.

So we can use kind of the...

So we're not interested.

It's a configuration problem, essentially.

So we don't want to look at the path.

We only look at the state that we're arriving in.

Okay?

And of course, this is exponential still.

But backtracking or depth-first search, that's exactly what depth-first search is wonderful

for.

We have a finite depth.

We don't need to make it finite by iteratively deepening or those kind of things.

And we can do linear space exponential type search.

Good.

And now the question, of course, is doing it in practice, seeing how that actually works.

So we're going to use depth-first search, which we're going to call backtracking search.

That is quite successful.

So you can do things like solve n queens, which is one thing we looked at, for things

like up to n equals 25.

I'm pretty sure that you can now probably do 27 or something like this, because computation

power gets bigger all the time.

Okay?

And then you get an algorithm like this one, which is just this idea of backtracking search

reformulated with original CSP components.